package _01_sort.leetcodeexerc.quicksort;

import _01_sort.SortUtil;
import org.junit.Test;

import java.util.Arrays;

import static _01_sort.SortUtil.swap;

/**
 * @author: mornd
 * @dateTime: 2023/6/24 - 9:54
 * 洛穆托单边循环快排
 * <p>
 * 每一轮选择最右侧元素做为基准点
 */
public class QuickSort1 {
    @Test
    public void test() {
        int[] arr = {7, 5, 2, 9, 3, 1, 0};
//        int[] arr = {4, 3, 7, 2, 9, 8, 1, 5};
        sort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    private void sort(int[] arr, int left, int right) {
        if (left < right) {
            // 基准点元素下标
            int p = partition(arr, left, right);
            sort(arr, left, p - 1);
            sort(arr, p + 1, right);
        }
    }

    private int partition(int[] arr, int left, int right) {
        int pv = arr[right];
        int i = left;
        int j = left;

        while (j < right) { // i找大的，j找小的
            if (arr[j] < pv) {
                if (i != j) {
                    swap(arr, i, j);
                }
                i++;
            }
            j++;
        }
        swap(arr, i, right);
        return i;
    }
}
